package com.Twenty_One;

import java.util.Arrays;

/**
 * 854. 相似度为 K 的字符串
 * 对于某些非负整数 k ，如果交换 s1 中两个字母的位置恰好 k 次，能够使结果字符串等于 s2 ，则认为字符串 s1 和 s2 的 相似度为 k 。
 *
 * 给你两个字母异位词 s1 和 s2 ，返回 s1 和 s2 的相似度 k 的最小值。
 *
 *  
 *
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode.cn/problems/k-similar-strings
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 *
 * 2022/09/21 15:25
 */

public class Solution854 {

    static int res=Integer.MAX_VALUE;

    public static int kSimilarity(String s1, String s2) {
        backtracking(s1,s2,0,s2.length(),0);
        return res;
    }

    public static void backtracking(String s1, String s2, int cur, int n, int ans){
        if (cur==n)
        {
            res=Math.min(ans,res);
            return;
        }
        if (ans>=res)
        {
            return;
        }
        StringBuilder sb= new StringBuilder(s2.toString());
        if (s1.charAt(cur)!=s2.charAt(cur))
        {
            for (int i=cur+1;i<n;i++)
            {
                if (s1.charAt(cur)==s2.charAt(i)&&s1.charAt(i)!=s2.charAt(i))
                {
                    //sb=swap(s2.toCharArray(),cur,i);
                    backtracking(s1, String.valueOf(swap(s2.toCharArray(),cur,i)),cur+1,n,ans+1);
                    //sb=swap(s2.toCharArray(),cur,i);
                }
            }
        }else
        {
            backtracking(s1, s2,cur+1,n,ans);

        }
    }
    public static StringBuilder swap(char[] s2, int left, int right)
    {
        char temp=s2[left];
        s2[left]=s2[right];
        s2[right]=temp;
        return new StringBuilder(String.valueOf(s2));
    }

    public static void main(String[] args) {
        System.out.println(kSimilarity("ab","ba"));
    }
}
